class AStar {
  static MAZE = [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
  ]
  static aStarSearch(start,end) {
    let openList = new Set();
    let closeList = new Set();
    openList.add(start);
    while (openList.size > 0) {
      let currentGrid = this.findMinGrid(openList)
      openList.delete(currentGrid)
      closeList.add(currentGrid);
      let neighbors = this.findNeighbors(currentGrid, openList, closeList)
      for (let grid of neighbors) {
        grid.initGrid(currentGrid, end);
        openList.add(grid)
      }
      for (let grid of openList) {
        if ((grid.x == end.x) && (grid.y == end.y)) {
                    return grid;
                }
      }
    }
    return null;
  }

  static findMinGrid(openList) {
    let tempGrid = [...openList][0];
    for (let grid of openList) {
      if (grid.f < tempGrid.f) {
        tempGrid = grid
      }
    }
    return tempGrid;
  }

  static findNeighbors(grid, openList, closeList) {
    let gridList = new Set();
    if(this.isValidGrid(grid.x, grid.y-1, openList, closeList)) {
      gridList.add(new Grid(grid.x, grid.y-1))
    }
    if (this.isValidGrid(grid.x, grid.y+1, openList, closeList)) {
        gridList.add(new Grid(grid.x, grid.y + 1));
    }
    if (this.isValidGrid(grid.x-1, grid.y, openList, closeList)) {
        gridList.add(new Grid(grid.x - 1, grid.y));
    }
    if (this.isValidGrid(grid.x+1, grid.y, openList, closeList)) {
        gridList.add(new Grid(grid.x + 1, grid.y));
    }
    return gridList;
  }
  static isValidGrid(x, y, openList, closeList) {
    //是否超过边界
    if (x < 0 || x >= this.MAZE.length || y < 0 || y >= this.MAZE[0].length) {
        return false;
    }
    //是否有障碍物
    if(this.MAZE[x][y] == 1){
        return false;
    }
    //是否已经在openList中
    if(this.containGrid(openList, x, y)){
        return false;
    }
    //是否已经在closeList中
    if(this.containGrid(closeList, x, y)){
        return false;
    }
    return true;
  }
  static containGrid(grids, x, y) {
    for (let grid of grids) {
      if ((grid.x == x) && (grid.y == y)) {
          return true;
      }
    }
    return false;
  }

}

class Grid {
  x;
  y;
  f;
  g;
  h;
  parent;
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
  initGrid(parent, end) {
    this.parent = parent;
    this.g = parent.g + 1;
    this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
    this.f = this.g + this.h;
  }
}

let startGrid = new Grid(2, 1)
let endGrid = new Grid(2, 5)
let resultGrid = AStar.aStarSearch(startGrid, endGrid)

let path = new Set();
while (resultGrid != null) {
  path.add(new Grid(resultGrid.x, resultGrid.y));
  resultGrid = resultGrid.parent;
}
let pathMap = ''
for(let i=0; i< AStar.MAZE.length; i++) {
  for (let j=0; j<AStar.MAZE[0].length; j++) {
    if (AStar.containGrid(path, i, j)) {
      pathMap += '*, '
    } else {
      pathMap += `${AStar.MAZE[i][j]}, `
    }
  }
  pathMap += '\n'
}
console.log(pathMap);

/**
0, 0, *, *, *, *, 0, 
0, 0, *, 1, 0, *, 0, 
0, *, *, 1, 0, *, 0, 
0, 0, 0, 1, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 
 */